package com.dragon.datastructure.sort;

/**
 * 冒泡排序
 * 通过两个相邻的元素进行比较，如果是逆序，则交换位置，一直到数组的最后一个元素，这样就能确定数组中的最大的那个元素。
 * 外圈需要循环的次数为： array.length - 1 次 ，为什么？ 因为最后一个元素不需要进行冒泡，已经排好了
 * <p>
 * 冒泡排序的缺点:
 * 1.时间复杂度为O(N^2)
 * 2.在数组元素比较随机的情况下，经常需要相邻元素进行交换位置
 * <p>
 * 冒泡排序的优点:
 * 但是冒泡有个很大的优点就是它可以检测整个数组是否已经有序，当某次遍历没有发生任何交换的时候你就可以提前终止了。也算是个小优化吧。
 *
 * @author dragon
 * @since 2019/12/23
 */
public class BubbleSort {

    public static void main(String[] args) {
        // 选择排序耗费的时间:31780毫秒
        Integer[] array = new Integer[80_000];
        for (int i = 0; i < array.length; i++) {
            array[i] = (int) (Math.random() * 800_000);
        }
        long startTime = System.currentTimeMillis();
        sort(array);
        long entTime = System.currentTimeMillis();
        System.out.println("选择排序耗费的时间:" + (entTime - startTime) + "毫秒");
    }

    /**
     * 冒泡排序
     *
     * @param source 被排序的数组
     * @param <T>    数组中的元素类型
     */
    public static <T extends Comparable<T>> void sort(T[] source) {
        if (source == null) {
            return;
        }
        boolean notExchange = true;
        for (int i = 0; i < source.length - 1; i++) {
            for (int j = 0; j < (source.length - i - 1); j++) {
                if (source[j].compareTo(source[j + 1]) > 0) {
                    notExchange = false;
                    T temp = source[j];
                    source[j] = source[j + 1];
                    source[j + 1] = temp;
                }
            }
            if (notExchange) {
                break;
            } else {
                notExchange = true;
            }
        }
    }
}
